package 正则表达式匹配;

class Solution {
    static int N = 400;
    static boolean[][] f = new boolean[N][N];

    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length(), k = 0;
        String t = " ";
        for (int i = 0; i < m; i++) {
            if (p.charAt(i) != '*' || t.charAt(k) != '*') {
                t += p.charAt(i);
                k++;
            }
        }
        s = " " + s;
        m = t.length()-1;
        p = t;

        f[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (j + 1 <= m && p.charAt(j + 1) == '*') {
                    continue;
                }
                if (i > 0 && p.charAt(j) != '*') {
                    f[i][j] = f[i - 1][j - 1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                } else if (p.charAt(j) == '*') {
                    f[i][j] = f[i][j - 2] || i > 0 && f[i - 1][j] && (s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
                }
            }
        }
        return f[n][m];
    }
}
